class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty())
            return 0;
        int res = 0;
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp_h(n, vector<int>(m));
        vector<vector<int>> dp_v(n, vector<int>(m));

        dp_h[0][0] = matrix[0][0];

        for(int i = 0; i < n; i++)
        {
            dp_h[i][0] = matrix[i][0]=='0' ? 0 : 1;
            // std::cout << dp_h[i][0] << std::endl;
            res = max(res, dp_h[i][0]);
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j < m; j++)
            {
                dp_h[i][j] = matrix[i][j]=='0' ? 0 : dp_h[i][j-1]+1;
                //std::cout << dp_h[i][j-1] << std::endl;
            }
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(dp_h[i][j] == 0)
                    continue;
                int area = dp_h[i][j];
                int min_side = dp_h[i][j];
                for(int k = i+1; k < n; k++)
                {
                    if(dp_h[k][j] == 0)
                        break;
                    min_side = min(min_side, dp_h[k][j]);
                    //std::cout << min_side << std::endl;
                    area = max(area, min_side*(k-i+1));
                }
                res = max(res, area);
            }
        }
        
        return res;
    }
};